<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode查找 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode查找</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-09-15 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%9F%A5%E6%89%BE/">查找</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>10.5k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>48 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="1-两数之和"><a href="#1-两数之和" class="headerlink" title="1. 两数之和"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/two-sum/" >1. 两数之和<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组 <code>nums</code> 和一个目标值 <code>target</code>，请你在该数组中找出和为目标值的那 <strong>两个</strong> 整数，并返回他们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">给定 nums = [<span class="number">2</span>, <span class="number">7</span>, <span class="number">11</span>, <span class="number">15</span>], target = <span class="number">9</span></span><br><span class="line"></span><br><span class="line">因为 nums[<span class="number">0</span>] + nums[<span class="number">1</span>] = <span class="number">2</span> + <span class="number">7</span> = <span class="number">9</span></span><br><span class="line">所以返回 [<span class="number">0</span>, <span class="number">1</span>]</span><br></pre></td></tr></table></figure>

<blockquote>
<p>平生不识<strong>TwoSum</strong>，做遍LeetCode也枉然</p>
</blockquote>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    <span class="keyword">int</span> length = nums.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; length - i; j++) &#123;</span><br><span class="line">            <span class="keyword">int</span> result = nums[i] + nums[i + j];</span><br><span class="line">            <span class="keyword">if</span> (result == target) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; i, i + j &#125;;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>最开始的做法，直接暴力求解，简单，但是效率很低，50ms，41% beats，其实在笔试或者其它对效率要求没那么严格的地方用暴力法也没毛病节约很多时间，能直接写出最优解肯定好，但是实在没办法了暴力法也不失为一种好方法，最优解可以下来后再研究。</p>
<p><strong>解法二</strong></p>
<p>hash查找</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="comment">//第一遍把所有的元素和索引存到hashMap中</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        map.put(nums[i],i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//再查找hash</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="comment">//不能重复所以 下标需要限制下</span></span><br><span class="line">        <span class="keyword">if</span>(map.containsKey(target-nums[i]) &amp;&amp; map.get(target-nums[i])!=i)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;i,map.get(target-nums[i])&#125;;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其实可以只hash一遍，hash两遍主要考虑顺序的问题。直接利用hashMap查找，效率很高。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum2(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="comment">//不能重复所以 下标需要限制下</span></span><br><span class="line">        <span class="keyword">if</span>(map.containsKey(target-nums[i]) &amp;&amp; map.get(target-nums[i])!=i)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;i,map.get(target-nums[i])&#125;;</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(nums[i],i);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>提交记录上最快的做法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    <span class="keyword">int</span> index;</span><br><span class="line">    <span class="keyword">int</span> indexArrayMax=<span class="number">2047</span>;</span><br><span class="line">    <span class="keyword">int</span>[] indexArrays=<span class="keyword">new</span> <span class="keyword">int</span>[indexArrayMax+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">int</span> diff;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        diff=target-nums[i];</span><br><span class="line">        <span class="comment">//i=0时索引无效,所以单独处理</span></span><br><span class="line">        <span class="keyword">if</span>(diff==nums[<span class="number">0</span>])&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;<span class="number">0</span>,i&#125;;</span><br><span class="line">        &#125;</span><br><span class="line">        index=diff&amp;indexArrayMax;</span><br><span class="line">        <span class="keyword">if</span>(indexArrays[index]!=<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;indexArrays[index],i&#125;;</span><br><span class="line">        &#125;</span><br><span class="line">        indexArrays[nums[i]&amp;indexArrayMax]=i;   </span><br><span class="line">    &#125;   </span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">2</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>没看懂。。。群里问了下，手动hash。。。。以后再来研究吧.</p>
<h2 id="349-两个数组的交集"><a href="#349-两个数组的交集" class="headerlink" title="349. 两个数组的交集"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/intersection-of-two-arrays/" >349. 两个数组的交集<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个数组，编写一个函数来计算它们的交集。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">1</span>], nums2 = [<span class="number">2</span>,<span class="number">2</span>]</span><br><span class="line">输出: [<span class="number">2</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">4</span>,<span class="number">9</span>,<span class="number">5</span>], nums2 = [<span class="number">9</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">8</span>,<span class="number">4</span>]</span><br><span class="line">输出: [<span class="number">9</span>,<span class="number">4</span>]</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ul>
<li>输出结果中的每个元素一定是唯一的。</li>
<li>我们可以不考虑输出结果的顺序。</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] intersection(<span class="keyword">int</span>[] nums1, <span class="keyword">int</span>[] nums2) &#123;</span><br><span class="line">    Set&lt;Integer&gt; s1=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    ArrayList&lt;Integer&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> a:nums1 ) &#123;</span><br><span class="line">        s1.add(a);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums2.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(s1.contains(nums2[i]))&#123;</span><br><span class="line">            res.add(nums2[i]);</span><br><span class="line">            s1.remove(nums2[i]);<span class="comment">//别忘了remove掉</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> [] res2=<span class="keyword">new</span> <span class="keyword">int</span>[res.size()];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;res.size();i++) &#123;</span><br><span class="line">        res2[i]=res.get(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res2;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>没啥好说的，这种题确实不难，仔细想想就可以</p>
<h2 id="350-两个数组的交集-II"><a href="#350-两个数组的交集-II" class="headerlink" title="350. 两个数组的交集 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/" >350. 两个数组的交集 II<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个数组，编写一个函数来计算它们的交集。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">1</span>], nums2 = [<span class="number">2</span>,<span class="number">2</span>]</span><br><span class="line">输出: [<span class="number">2</span>,<span class="number">2</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">4</span>,<span class="number">9</span>,<span class="number">5</span>], nums2 = [<span class="number">9</span>,<span class="number">4</span>,<span class="number">9</span>,<span class="number">8</span>,<span class="number">4</span>]</span><br><span class="line">输出: [<span class="number">4</span>,<span class="number">9</span>]</span><br></pre></td></tr></table></figure>

<p><strong>说明：</strong></p>
<ul>
<li>输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。</li>
<li>我们可以不考虑输出结果的顺序。</li>
</ul>
<p><strong>进阶:</strong></p>
<ul>
<li>如果给定的数组已经排好序呢？你将如何优化你的算法？</li>
<li>如果 nums1 的大小比 nums2 小很多，哪种方法更优？</li>
<li>如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？</li>
</ul>
<p><strong>解法一</strong></p>
<p>这题和上面的区别就是需要输出所有的交集，重复的也算，所以可以用map的结构记录字符出现的次数</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] intersect(<span class="keyword">int</span>[] nums1, <span class="keyword">int</span>[] nums2) &#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums1.length;i++) &#123;</span><br><span class="line">        map.put(nums1[i],map.getOrDefault(nums1[i],<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    ArrayList&lt;Integer&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums2.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (map.containsKey(nums2[i])) &#123;</span><br><span class="line">            <span class="keyword">if</span> (map.get(nums2[i])!=<span class="number">0</span>) &#123;</span><br><span class="line">                <span class="comment">//有交集</span></span><br><span class="line">                res.add(nums2[i]); <span class="comment">//添加到结果中</span></span><br><span class="line">                map.put(nums2[i],map.get(nums2[i])-<span class="number">1</span>); <span class="comment">//map映射减一</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> []res2=<span class="keyword">new</span> <span class="keyword">int</span>[res.size()];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;res2.length;i++) &#123;</span><br><span class="line">        res2[i]=res.get(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res2;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>思路也很直白，和上一题的做法类似</p>
<p><strong>进阶</strong></p>
<p><strong>Q1:</strong> 排好序的话就可以直接利用双指针，两个指针分别指向两个数组的头，相等就加入list，不相等就移动小的哪一个，直到有一个指针走到末尾</p>
<p><strong>Q2:</strong> 这个就很明显了，肯定先把小的哪一个用map映射起来，这样map查找的效率会更高 ？</p>
<p><strong>Q3:</strong> 这个参考英文版的 <a class="link"   target="_blank" rel="noopener" href="https://leetcode.com/problems/intersection-of-two-arrays-ii/discuss/82243/Solution-to-3rd-follow-up-question" >讨论区<i class="fas fa-external-link-alt"></i></a> </p>
<h2 id="242-有效的字母异位词"><a href="#242-有效的字母异位词" class="headerlink" title="242. 有效的字母异位词"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/valid-anagram/" >242. 有效的字母异位词<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: s = <span class="string">&quot;anagram&quot;</span>, t = <span class="string">&quot;nagaram&quot;</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: s = <span class="string">&quot;rat&quot;</span>, t = <span class="string">&quot;car&quot;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ul>
<li>你可以假设字符串只包含小写字母。</li>
</ul>
<p><strong>进阶:</strong></p>
<ul>
<li>如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isAnagram</span><span class="params">(String s, String t)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s.length()!=t.length())<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">256</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        freq[s.charAt(i)]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>,match=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> a:freq) &#123;</span><br><span class="line">        <span class="keyword">if</span>(a!=<span class="number">0</span>)&#123;</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;t.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(freq[t.charAt(i)]&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            freq[t.charAt(i)]--;</span><br><span class="line">            <span class="keyword">if</span>(freq[t.charAt(i)]==<span class="number">0</span>)&#123;</span><br><span class="line">                match++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> match==count;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这里其实空间还可以优化，题目说了字符串只包含小写字符所以只需要26个int就行了，可以在freq操作的时候 <code>-&#39;A&#39;</code> 优化空间</p>
<p><strong>进阶</strong></p>
<p>字符包含<code>unicode</code> 的话如果再使用int数组就不合适了，这个范围会变得很大，更加通用的方式是采用<code>HashMap</code></p>
<h2 id="1160-拼写单词"><a href="#1160-拼写单词" class="headerlink" title="1160. 拼写单词"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/" >1160. 拼写单词<i class="fas fa-external-link-alt"></i></a></h2><p>给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。</p>
<p>假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。</p>
<p><strong>注意：</strong>每次拼写时，chars 中的每个字母都只能用一次。</p>
<p>返回词汇表 words 中你掌握的所有单词的 长度之和。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：words = [<span class="string">&quot;cat&quot;</span>,<span class="string">&quot;bt&quot;</span>,<span class="string">&quot;hat&quot;</span>,<span class="string">&quot;tree&quot;</span>], chars = <span class="string">&quot;atach&quot;</span></span><br><span class="line">输出：<span class="number">6</span></span><br><span class="line">解释： </span><br><span class="line">可以形成字符串 <span class="string">&quot;cat&quot;</span> 和 <span class="string">&quot;hat&quot;</span>，所以答案是 <span class="number">3</span> + <span class="number">3</span> = <span class="number">6</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：words = [<span class="string">&quot;hello&quot;</span>,<span class="string">&quot;world&quot;</span>,<span class="string">&quot;leetcode&quot;</span>], chars = <span class="string">&quot;welldonehoneyr&quot;</span></span><br><span class="line">输出：<span class="number">10</span></span><br><span class="line">解释：</span><br><span class="line">可以形成字符串 <span class="string">&quot;hello&quot;</span> 和 <span class="string">&quot;world&quot;</span>，所以答案是 <span class="number">5</span> + <span class="number">5</span> = <span class="number">10</span>。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= words.length &lt;= 1000</code></li>
<li><code>1 &lt;= words[i].length, chars.length &lt;= 100</code></li>
<li>所有字符串中都仅包含小写英文字母</li>
</ul>
<p><strong>解法一</strong></p>
<p>大晚上题目都没看清就开始写！！题目说的是每次只能使用一次！！！</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">countCharacters</span><span class="params">(String[] words, String chars)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] hash=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;chars.length();i++) &#123;</span><br><span class="line">        hash[chars.charAt(i)-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] temp=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;words.length;i++) &#123;</span><br><span class="line">        String word=words[i];</span><br><span class="line">        Arrays.fill(temp,<span class="number">0</span>);</span><br><span class="line">        <span class="keyword">boolean</span> flag=<span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;word.length();j++) &#123;</span><br><span class="line">            temp[word.charAt(j)-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">            <span class="keyword">if</span>(temp[word.charAt(j)-<span class="string">&#x27;a&#x27;</span>]&gt;hash[word.charAt(j)-<span class="string">&#x27;a&#x27;</span>])&#123;</span><br><span class="line">                flag=<span class="keyword">false</span>;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        res+=flag?word.length():<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>一开始用的arraycopy然后减减，差不多</p>
<h2 id="202-快乐数"><a href="#202-快乐数" class="headerlink" title="202. 快乐数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/happy-number/" >202. 快乐数<i class="fas fa-external-link-alt"></i></a></h2><p>编写一个算法来判断一个数是不是“快乐数”。</p>
<p>一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。</p>
<p><strong>示例:</strong> </p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">19</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br><span class="line">解释: </span><br><span class="line"><span class="number">12</span> + <span class="number">92</span> = <span class="number">82</span></span><br><span class="line"><span class="number">82</span> + <span class="number">22</span> = <span class="number">68</span></span><br><span class="line"><span class="number">62</span> + <span class="number">82</span> = <span class="number">100</span></span><br><span class="line"><span class="number">12</span> + <span class="number">02</span> + <span class="number">02</span> = <span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isHappy</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">char</span>[] nums=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">int</span> sum=n;</span><br><span class="line">    <span class="keyword">while</span>(<span class="keyword">true</span>) &#123;</span><br><span class="line">        nums=String.valueOf(sum).toCharArray();</span><br><span class="line">        sum=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">            sum+=(nums[i]-<span class="number">48</span>)*(nums[i]-<span class="number">48</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (sum==<span class="number">4</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (sum==<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>找到了规律，所有不快乐的数(😅，都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环，可以直接在sum和这些值相等的时候就return我懒得写那么多，比较取巧但是效率还是挺高的</p>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">isHappy</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">char</span>[] nums=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">int</span> sum=n;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">while</span>(<span class="keyword">true</span>) &#123;</span><br><span class="line">        nums=String.valueOf(sum).toCharArray();</span><br><span class="line">        sum=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">            sum+=(nums[i]-<span class="number">48</span>)*(nums[i]-<span class="number">48</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (sum==<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (set.contain(sum))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            set.add(sum);    </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这种做法就比较常规，也是符合这篇主题<strong>查找</strong>的解法，代码比较简单就不啰嗦了</p>
<h2 id="290-单词规律"><a href="#290-单词规律" class="headerlink" title="290. 单词规律"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-pattern/" >290. 单词规律<i class="fas fa-external-link-alt"></i></a></h2><p>给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。</p>
<p>这里的 <strong>遵循</strong> 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。</p>
<p><strong>示例1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: pattern = <span class="string">&quot;abba&quot;</span>, str = <span class="string">&quot;dog cat cat dog&quot;</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:pattern = <span class="string">&quot;abba&quot;</span>, str = <span class="string">&quot;dog cat cat fish&quot;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: pattern = <span class="string">&quot;aaaa&quot;</span>, str = <span class="string">&quot;dog cat cat dog&quot;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 4:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: pattern = <span class="string">&quot;abba&quot;</span>, str = <span class="string">&quot;dog dog dog dog&quot;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong><br>你可以假设 <code>pattern</code> 只包含小写字母， <code>str</code> 包含了由单个空格分隔的小写字母</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">wordPattern</span><span class="params">(String pattern, String str)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Character,String&gt; map=<span class="keyword">new</span> LinkedHashMap&lt;&gt;();</span><br><span class="line">    String[] strs=str.split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">    <span class="keyword">char</span>[] p=pattern.toCharArray();</span><br><span class="line">    <span class="keyword">if</span> (strs.length!=p.length) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;p.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (map.containsKey(p[i])) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!map.get(p[i]).equals(strs[i])) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//这里直接和前一个比较的，正确做法是用map.containsValue判断是否已经添加</span></span><br><span class="line">            <span class="comment">/*if (strs[i].equals(strs[i-1])) &#123;</span></span><br><span class="line"><span class="comment">                return false;</span></span><br><span class="line"><span class="comment">            &#125;*/</span></span><br><span class="line">            <span class="keyword">if</span> (map.containsValue(strs[i])) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;           </span><br><span class="line">            &#125;</span><br><span class="line">            map.put(p[i],strs[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>很简单的题，需要对两个字符串的模式进行匹配，借助Hash表直接将两个String进行一对一的映射，既然要匹配那么<code>同一个key字符对应的value字符肯定是一样的</code>，还有一点需要注意的是在遇到一个新的key字符的时候，需要判断对应位置的value字符出现过没有，出现过就直接return false，这一点第一遍的时候没考虑到，<code>不同的key字符对应的value字符肯定是不一样的</code></p>
<blockquote>
<p>因为第一次没考虑到第二种情况，提交后竟然跑过了<code>31/33</code> 个case，然后就感觉这题case可能有点问题，然后自己写了个错的算法居然也跑过了，具体的代码在上面的注释中，感兴趣的可以去试试，我已经提交case了但是还没回应我</p>
</blockquote>
<h2 id="205-同构字符串"><a href="#205-同构字符串" class="headerlink" title="205. 同构字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/isomorphic-strings/" >205. 同构字符串<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个字符串 s 和 t，判断它们是否是同构的。</p>
<p>如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。</p>
<p>所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: s = <span class="string">&quot;egg&quot;</span>, t = <span class="string">&quot;add&quot;</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: s = <span class="string">&quot;foo&quot;</span>, t = <span class="string">&quot;bar&quot;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: s = <span class="string">&quot;paper&quot;</span>, t = <span class="string">&quot;title&quot;</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ul>
<li>你可以假设 s 和 t 具有相同的长度。</li>
</ul>
<p><strong>解法一</strong></p>
<p>这题和上面一模一样，Hash表的解法就不写了，这题都是单个的字符，可以不用Hash表，可以用数组优化</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isIsomorphic2</span><span class="params">(String s, String t)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s.length()!=t.length()) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] key=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">256</span>];</span><br><span class="line">    <span class="keyword">int</span>[] value=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">256</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> cs=s.charAt(i);</span><br><span class="line">        <span class="keyword">int</span> ct=t.charAt(i);</span><br><span class="line">        <span class="keyword">if</span>(key[cs]!=<span class="number">0</span>)&#123; <span class="comment">//cs出现过</span></span><br><span class="line">            <span class="keyword">if</span> (key[cs]!=ct) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;<span class="comment">//cs没出现过</span></span><br><span class="line">            <span class="keyword">if</span> (value[ct]!=<span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            key[cs]=ct;</span><br><span class="line">            value[ct]=cs;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>💬 同样的，这题和上面的290一样，case也有问题，直接和前一个字符比较就可以过</p>
<h2 id="454-四数相加-II"><a href="#454-四数相加-II" class="headerlink" title="454. 四数相加 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/4sum-ii/" >454. 四数相加 II<i class="fas fa-external-link-alt"></i></a></h2><p>给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。</p>
<p>为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 <code>0 ≤ N ≤ 500</code> 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。</p>
<p><strong>例如:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">A = [ <span class="number">1</span>, <span class="number">2</span>]</span><br><span class="line">B = [-<span class="number">2</span>,-<span class="number">1</span>]</span><br><span class="line">C = [-<span class="number">1</span>, <span class="number">2</span>]</span><br><span class="line">D = [ <span class="number">0</span>, <span class="number">2</span>]</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">两个元组如下:</span><br><span class="line"></span><br><span class="line"><span class="number">1.</span> (<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">1</span>) -&gt; A[<span class="number">0</span>] + B[<span class="number">0</span>] + C[<span class="number">0</span>] + D[<span class="number">1</span>] = <span class="number">1</span> + (-<span class="number">2</span>) + (-<span class="number">1</span>) + <span class="number">2</span> = <span class="number">0</span></span><br><span class="line"><span class="number">2.</span> (<span class="number">1</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>) -&gt; A[<span class="number">1</span>] + B[<span class="number">1</span>] + C[<span class="number">0</span>] + D[<span class="number">0</span>] = <span class="number">2</span> + (-<span class="number">1</span>) + (-<span class="number">1</span>) + <span class="number">0</span> = <span class="number">0</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这题其实看数据规模就知道应该写一个什么样复杂度的算法了<code>0~500</code>，暴力的话会很恐怖<code>O(N^4)</code>，这里可以考虑将其中一个放到hash表中，然后遍历其他的3个，时间复杂度优化到了<code>O(N^3)</code>，但是时间复杂度还是很恐怖，所以可以考虑将两个数组的和放到hash表中，这样就可以将时间复杂度优化到<code>O(N^2)</code></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">fourSumCount</span><span class="params">(<span class="keyword">int</span>[] A, <span class="keyword">int</span>[] B, <span class="keyword">int</span>[] C, <span class="keyword">int</span>[] D)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;C.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;D.length;j++) &#123;</span><br><span class="line">            <span class="keyword">int</span> key=C[i]+D[j];</span><br><span class="line">            map.put(key,map.getOrDefault(key,<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;B.length;j++) &#123;</span><br><span class="line">            <span class="keyword">int</span> key=A[i]+B[j];</span><br><span class="line">            <span class="keyword">if</span>(map.containsKey(-key))&#123;</span><br><span class="line">                res+=map.get(-key);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="451-根据字符出现频率排序"><a href="#451-根据字符出现频率排序" class="headerlink" title="451. 根据字符出现频率排序"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sort-characters-by-frequency/" >451. 根据字符出现频率排序<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个字符串，请将字符串里的字符按照出现的频率降序排列。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line"><span class="string">&quot;tree&quot;</span></span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="string">&quot;eert&quot;</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line"><span class="string">&#x27;e&#x27;</span>出现两次，<span class="string">&#x27;r&#x27;</span>和<span class="string">&#x27;t&#x27;</span>都只出现一次。</span><br><span class="line">因此<span class="string">&#x27;e&#x27;</span>必须出现在<span class="string">&#x27;r&#x27;</span>和<span class="string">&#x27;t&#x27;</span>之前。此外，<span class="string">&quot;eetr&quot;</span>也是一个有效的答案。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line"><span class="string">&quot;cccaaa&quot;</span></span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="string">&quot;cccaaa&quot;</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line"><span class="string">&#x27;c&#x27;</span>和<span class="string">&#x27;a&#x27;</span>都出现三次。此外，<span class="string">&quot;aaaccc&quot;</span>也是有效的答案。</span><br><span class="line">注意<span class="string">&quot;cacaca&quot;</span>是不正确的，因为相同的字母必须放在一起。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line"><span class="string">&quot;Aabb&quot;</span></span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="string">&quot;bbAa&quot;</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">此外，<span class="string">&quot;bbaA&quot;</span>也是一个有效的答案，但<span class="string">&quot;Aabb&quot;</span>是不正确的。</span><br><span class="line">注意<span class="string">&#x27;A&#x27;</span>和<span class="string">&#x27;a&#x27;</span>被认为是两种不同的字符。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title">frequencySort</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || s.length()&lt;<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> s;</span><br><span class="line">    &#125;</span><br><span class="line">    HashMap&lt;Character,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        map.put(s.charAt(i),map.getOrDefault(s.charAt(i),<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    ArrayList&lt;HashMap.Entry&gt; list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(HashMap.Entry entry:map.entrySet())&#123;</span><br><span class="line">        list.add(entry);</span><br><span class="line">    &#125;</span><br><span class="line">    list.sort((e1,e2)-&gt;(Integer)e2.getValue()-(Integer)e1.getValue());</span><br><span class="line">    StringBuilder res=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; list.size(); i++) &#123;</span><br><span class="line">        Integer value = (Integer)list.get(i).getValue();</span><br><span class="line">        <span class="keyword">while</span> (value&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            res.append(list.get(i).getKey());</span><br><span class="line">            value--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题其实也是TopK问题，直接的想法就是用hashMap统计各个字符出现的个数，然后排序再拼接为结果，其实这题一开始是TLE了的，一开始没注意直接用的String拼接的，效率很低，改用StringBuilder后就过了，虽然效率还是很低 138ms，垫底</p>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  <span class="keyword">static</span> String <span class="title">frequencySort2</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || s.length()&lt;<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> s;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">256</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        freq[s.charAt(i)]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] freq_bak=freq.clone();</span><br><span class="line">    Arrays.sort(freq);</span><br><span class="line">    StringBuilder res=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="comment">//从大到小</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">255</span>; i&gt;=<span class="number">0</span> &amp;&amp; freq[i]!=<span class="number">0</span>; i--) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;<span class="number">255</span>;j++) &#123;</span><br><span class="line">            <span class="comment">//找到原数组中对应的字符</span></span><br><span class="line">            <span class="comment">//只要出现次数一样的就行了</span></span><br><span class="line">            <span class="keyword">if</span>(freq_bak[j]==freq[i])&#123;</span><br><span class="line">                <span class="comment">//根据freq_bak[j]构造结果</span></span><br><span class="line">                <span class="keyword">while</span>(freq_bak[j]&gt;<span class="number">0</span>)&#123;</span><br><span class="line">                    res.append((<span class="keyword">char</span>)j);</span><br><span class="line">                    freq_bak[j]--;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>15ms，90% 其实思路和上面是一样的，都是统计数量后进行排序，然后重建字符串，但是用数组的方式明显会比HashMap效率会更高的多，后面的两层循环都是在常数时间内，主要是重建字符串和排序消耗时间，时间复杂度应该是<code>O(NlogN)</code></p>
<p><strong>解法三</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  <span class="keyword">static</span> String <span class="title">frequencySort3</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s==<span class="keyword">null</span> || s.length()&lt;<span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> s;</span><br><span class="line">    &#125;</span><br><span class="line">    ArrayList&lt;Character&gt; [] bucket=<span class="keyword">new</span> ArrayList[s.length()+<span class="number">1</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">256</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        freq[s.charAt(i)]++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bucket[freq[s.charAt(i)]]==<span class="keyword">null</span>) &#123;</span><br><span class="line">            bucket[freq[s.charAt(i)]]=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//每个元素只进入一次</span></span><br><span class="line">        <span class="keyword">if</span> (!bucket[freq[s.charAt(i)]].contains(s.charAt(i))) &#123;</span><br><span class="line">            bucket[freq[s.charAt(i)]].add(s.charAt(i));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; </span><br><span class="line">    <span class="comment">//printArray(bucket);</span></span><br><span class="line">    StringBuilder res=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=bucket.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--) &#123;</span><br><span class="line">        <span class="comment">//过滤0</span></span><br><span class="line">        <span class="keyword">if</span> (bucket[i]==<span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//出现i次的字符list</span></span><br><span class="line">        ArrayList&lt;Character&gt; temp=bucket[i];</span><br><span class="line">        <span class="comment">//遍历出现次数相同的list()</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;temp.size();j++) &#123; </span><br><span class="line">            <span class="comment">//遍历出现的次数</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> count=<span class="number">0</span>;count&lt;i;count++) &#123;</span><br><span class="line">                res.append(temp.get(j));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>50ms，50% 这个是根据 <a href="http://imlgw.top/2019/05/04/leetcode-shu-zu-tag/#347-%E5%89%8D-K-%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0">前k个高频元素</a> 中桶排序的解法来的，当然这里并不是最优解，只是一种思路，其实写起来还是挺麻烦的，时间复杂度略高，主要是在桶排序的时候添加元素做不到O(N)需要判断元素是否添加，一个元素只能在list中添加一次，否则后面重建字符串的时候就会有问题</p>
<h2 id="49-字母异位词分组"><a href="#49-字母异位词分组" class="headerlink" title="49. 字母异位词分组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/group-anagrams/" >49. 字母异位词分组<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="string">&quot;eat&quot;</span>, <span class="string">&quot;tea&quot;</span>, <span class="string">&quot;tan&quot;</span>, <span class="string">&quot;ate&quot;</span>, <span class="string">&quot;nat&quot;</span>, <span class="string">&quot;bat&quot;</span>],</span><br><span class="line">输出:</span><br><span class="line">[</span><br><span class="line">  [<span class="string">&quot;ate&quot;</span>,<span class="string">&quot;eat&quot;</span>,<span class="string">&quot;tea&quot;</span>],</span><br><span class="line">  [<span class="string">&quot;nat&quot;</span>,<span class="string">&quot;tan&quot;</span>],</span><br><span class="line">  [<span class="string">&quot;bat&quot;</span>]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<p><strong>说明：</strong></p>
<ul>
<li>所有输入均为小写字母</li>
<li>不考虑答案输出的顺序</li>
</ul>
<p><strong>解法一</strong></p>
<p>算是暴力法了，借助上面的同构题思路来遍历判断</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) &#123;</span><br><span class="line">    ArrayList&lt;List&lt;String&gt;&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;strs.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="string">&quot;7&quot;</span>==strs[i]) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        ArrayList&lt;String&gt; group=<span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">        group.add(strs[i]);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;strs.length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (<span class="string">&quot;7&quot;</span>==strs[j]) &#123;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(isAnagram(strs[i],strs[j]))&#123;</span><br><span class="line">                group.add(strs[j]);</span><br><span class="line">                <span class="comment">//有分组了</span></span><br><span class="line">                strs[j]=<span class="string">&quot;7&quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        res.add(group);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isAnagram</span><span class="params">(String str1,String str2)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(str1.length()!=str2.length())&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;str1.length();i++) &#123;</span><br><span class="line">        freq[str1.charAt(i)-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;str2.length();i++) &#123;</span><br><span class="line">        freq[str2.charAt(i)-<span class="string">&#x27;a&#x27;</span>]--;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;freq.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (freq[i]!=<span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看到里面有一个<code>7</code> 其实没什么含义就是为了表示这个字符已经有分组了，这里一开始我是用的equals来比较的这个7结果超时了，然后换成了==勉强跑过了，可能是个例，因为我后来用boolean数组也没跑过。。。</p>
<blockquote>
<p>这里用==可以比较的原因可能是strs和字面量 “7”都在字符常量池中，但是这里并不建议这样比较，这里可以说是个反例了，比较字符串请用<code>equals</code> ！！！</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) &#123;</span><br><span class="line">    ArrayList&lt;List&lt;String&gt;&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">boolean</span>[] flag=<span class="keyword">new</span> <span class="keyword">boolean</span>[strs.length()];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;strs.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (flag[i]) <span class="keyword">continue</span>;</span><br><span class="line">        ArrayList&lt;String&gt; group=<span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">        group.add(strs[i]);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;strs.length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(flag[j])<span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">if</span>(isAnagram(strs[i],strs[j]))&#123;</span><br><span class="line">                group.add(strs[j]);</span><br><span class="line">                flag[j]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        res.add(group);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<p>利用排序结果来作为key，将排序结果相同的str映射到一起</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//排序解法</span></span><br><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) &#123;</span><br><span class="line">    HashMap&lt;String,List&lt;String&gt;&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;strs.length;i++) &#123;</span><br><span class="line">        <span class="keyword">char</span>[] strs_i=strs[i].toCharArray();</span><br><span class="line">        <span class="comment">//排序，将结果作为key</span></span><br><span class="line">        Arrays.sort(strs_i);</span><br><span class="line">        String key=String.valueOf(strs_i);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span>(map.containsKey(key))&#123;</span><br><span class="line">            <span class="comment">//存在同构的key，直接添加进去</span></span><br><span class="line">            map.get(key).add(strs[i]);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//不存在就创建一个，然后将自己添加进去</span></span><br><span class="line">            map.put(key,<span class="keyword">new</span> ArrayList&lt;&gt;());</span><br><span class="line">            map.get(key).add(strs[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> ArrayList(map.values());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>时间复杂度<code>O(NKlogK)</code>，K为字符数组中最长的字符串，<code>O(KlogK)</code> 是给这个字符串排序的结果</p>
<p><strong>解法三</strong></p>
<p>根据出现频次构成的字符串作为key，比如<code>aba</code>以及所有的异位词都会被映射为<code>2#1#</code> </p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) &#123;</span><br><span class="line">    HashMap&lt;String,List&lt;String&gt;&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span>[] freq=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">26</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;strs.length;i++) &#123;</span><br><span class="line">        <span class="comment">//Arrays.fill(freq,0);</span></span><br><span class="line">        <span class="comment">//统计字符出现的频次</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;strs[i].length();j++) &#123;</span><br><span class="line">            freq[strs[i].charAt(j)-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//构建唯一映射的key</span></span><br><span class="line">        StringBuilder key=<span class="keyword">new</span> StringBuilder();</span><br><span class="line">        <span class="comment">//这个其实类似桶排序,依次取abcde...</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;<span class="number">26</span>;j++) &#123;</span><br><span class="line">            key.append(freq[j]);</span><br><span class="line">            <span class="comment">//这个#很关键,为了防止重复,因为有的字符可能出现两位数的次数,仅仅对比数字是无法确定的</span></span><br><span class="line">            key.append(<span class="string">&quot;#&quot;</span>);</span><br><span class="line">            <span class="comment">//重置为0方便后面重复使用</span></span><br><span class="line">            freq[j]=<span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        String skey=key.toString();</span><br><span class="line">        <span class="keyword">if</span>(map.containsKey(skey))&#123;</span><br><span class="line">            map.get(skey).add(strs[i]);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            map.put(skey,<span class="keyword">new</span> ArrayList());</span><br><span class="line">            map.get(skey).add(strs[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> ArrayList(map.values());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>45ms，21% 时间复杂度<code>O(NK)</code> K为字符数组中最长的字符串的长度，很玄学，讲道理应该不会这么慢，看了leetcode上前几名跟我的差不多，开始做的时候直接用 <code>StringBuilder</code> 对象作为了key结果肯定不对，StringBuilder没有覆盖equals方法，key永远不会相等，每次都是新的key</p>
<p><strong>解法四</strong></p>
<p><strong>算术基本定理</strong>，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) &#123;</span><br><span class="line">    HashMap&lt;Integer, List&lt;String&gt;&gt; hash = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="comment">//每个字母对应一个质数</span></span><br><span class="line">    <span class="keyword">int</span>[] prime = &#123; <span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">7</span>, <span class="number">11</span>, <span class="number">13</span>, <span class="number">17</span>, <span class="number">19</span>, <span class="number">23</span>, <span class="number">29</span>, <span class="number">31</span>, <span class="number">41</span>, <span class="number">43</span>, <span class="number">47</span>, <span class="number">53</span>, <span class="number">59</span>, <span class="number">61</span>, <span class="number">67</span>, <span class="number">71</span>, <span class="number">73</span>, <span class="number">79</span>, <span class="number">83</span>, <span class="number">89</span>, <span class="number">97</span>, <span class="number">101</span>, <span class="number">103</span> &#125;;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; strs.length; i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> key = <span class="number">1</span>;</span><br><span class="line">        <span class="comment">//累乘得到 key</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; strs[i].length(); j++) &#123;</span><br><span class="line">            key *= prime[strs[i].charAt(j) - <span class="string">&#x27;a&#x27;</span>];</span><br><span class="line">        &#125; </span><br><span class="line">        <span class="keyword">if</span> (hash.containsKey(key)) &#123;</span><br><span class="line">            hash.get(key).add(strs[i]);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            List&lt;String&gt; temp = <span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">            temp.add(strs[i]);</span><br><span class="line">            hash.put(key, temp);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> ArrayList&lt;List&lt;String&gt;&gt;(hash.values());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>时间复杂度<code>O(NK)</code>，强的8行</p>
<blockquote>
<p>分析完上面三种解法后其实很同意得出这题的关键：<code>给同组的异位词找到一个相同的映射key</code>，尽量的缩短求这个映射的时间就可优化整个算法</p>
</blockquote>
<h2 id="447-回旋镖的数量"><a href="#447-回旋镖的数量" class="headerlink" title="447. 回旋镖的数量"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-boomerangs/" >447. 回旋镖的数量<i class="fas fa-external-link-alt"></i></a></h2><p>给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 <code>(i, j, k)</code> ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（<strong>需要考虑元组的顺序</strong>）</p>
<p>找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 <code>[-10000, 10000]</code> 中。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">[[<span class="number">0</span>,<span class="number">0</span>],[<span class="number">1</span>,<span class="number">0</span>],[<span class="number">2</span>,<span class="number">0</span>]]</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line"><span class="number">2</span></span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">两个回旋镖为 [[<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>],[<span class="number">2</span>,<span class="number">0</span>]] 和 [[<span class="number">1</span>,<span class="number">0</span>],[<span class="number">2</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>]]</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">numberOfBoomerangs</span><span class="params">(<span class="keyword">int</span>[][] points)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;points.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;points.length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (i!=j)&#123;</span><br><span class="line">                <span class="keyword">int</span> dis=dis(points[i],points[j]);</span><br><span class="line">                map.put(dis,map.getOrDefault(dis,<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//C2m 组合问题</span></span><br><span class="line">        <span class="keyword">for</span> (Integer count:map.values()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (count&gt;<span class="number">1</span>) &#123;</span><br><span class="line">                res+=count*(count-<span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        map.clear();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">dis</span><span class="params">(<span class="keyword">int</span>[] a,<span class="keyword">int</span>[] b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a[<span class="number">0</span>]-b[<span class="number">0</span>])*(a[<span class="number">0</span>]-b[<span class="number">0</span>])+(a[<span class="number">1</span>]-b[<span class="number">1</span>])*(a[<span class="number">1</span>]-b[<span class="number">1</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>看一下给的数据量<code>500</code>就知道复杂度只能是<code>O(N^2)</code> 的，用Hash表统计到当前点的距离相同的点有多少个，然后利用组合数求多少种组合，一开始并没有想到这种方法，我想的是利用坐标系的对称来做，太菜了</p>
<p>这里还有个小细节，一开始将HashMap的创建放在内循环中，发现效率很低，300ms左右，然后将创建HashMap移出去后用clear清空，瞬间快了100ms左右，创建HashMap的成本果然还是挺大的</p>
<p>这题其实还可以减少内循环的数量，</p>
<h2 id="217-存在重复元素"><a href="#217-存在重复元素" class="headerlink" title="217. 存在重复元素"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/contains-duplicate/" >217. 存在重复元素<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组，判断是否存在重复元素。</p>
<p>如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">1</span>]</span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>]</span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">2</span>]</span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>借助Hash表，很简单的题</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">containsDuplicate</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (set.contains(nums[i])) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        set.add(nums[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实还可以优化下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">containsDuplicate</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!set.add(nums[i])) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>set.add()</code> 本身就带有返回值，可以减少很多判断，这题还有一个进阶版 <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/contains-duplicate-ii/" >219. 存在重复元素 II<i class="fas fa-external-link-alt"></i></a> 也不难，我放到 <a href="http://imlgw.top/2019/07/20/leetcode-hua-dong-chuang-kou-tag/#3-%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2">滑动窗口专题</a> 中去了</p>
<h2 id="220-存在重复元素-III"><a href="#220-存在重复元素-III" class="headerlink" title="220. 存在重复元素 III"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/contains-duplicate-iii/" >220. 存在重复元素 III<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 <code>nums [i]</code> 和 <code>nums [j]</code> 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 k</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">1</span>], k = <span class="number">3</span>, t = <span class="number">0</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums = [<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>], k = <span class="number">1</span>, t = <span class="number">2</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums = [<span class="number">1</span>,<span class="number">5</span>,<span class="number">9</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">9</span>], k = <span class="number">2</span>, t = <span class="number">3</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这里其实可以算难题了，通过率只有20%，利用Java中提供的TreeMap，有顺序而且插入和删除等操作效率都很高（logN），然后查找指定范围的元素，看符不符合题目要求</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsNearbyAlmostDuplicate</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k, <span class="keyword">int</span> t)</span> </span>&#123;</span><br><span class="line">    TreeSet&lt;Integer&gt; set=<span class="keyword">new</span> TreeSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="comment">//大于nums[i]的最小元素</span></span><br><span class="line">        Integer ceiling=set.ceiling(nums[i]);</span><br><span class="line">        <span class="comment">//小于nums[i]的最大元素</span></span><br><span class="line">        Integer floor=set.floor(nums[i]);</span><br><span class="line">        <span class="comment">//防止溢出</span></span><br><span class="line">        <span class="keyword">long</span> temp1=Long.valueOf(nums[i])+Long.valueOf(t);</span><br><span class="line">        <span class="keyword">long</span> temp2=Long.valueOf(nums[i])-Long.valueOf(t);</span><br><span class="line">        <span class="keyword">if</span>((ceiling!=<span class="keyword">null</span> &amp;&amp; ceiling&lt;=temp1) || (floor!=<span class="keyword">null</span> &amp;&amp; floor&gt;=temp2)) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        set.add(nums[i]);</span><br><span class="line">        <span class="keyword">if</span> (set.size()&gt;k) &#123;</span><br><span class="line">            <span class="comment">//移除左边界</span></span><br><span class="line">            set.remove(nums[i-k]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>72ms，5%左右，整体时间复杂度<code>O(NlogN)</code> </p>
<p><strong>解法二</strong></p>
<p>看了下评论区，发现其实可以直接和两个边界<code>[u-t,u+t]</code>比较，只要两个数都在这个范围内就一定符合条件，这样可以少一次查找的操作，效率有很大提升</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsNearbyAlmostDuplicate2</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k, <span class="keyword">int</span> t)</span> </span>&#123;</span><br><span class="line">    TreeSet&lt;Long&gt; set=<span class="keyword">new</span> TreeSet&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="comment">//大于nums[i]-t的最小元素</span></span><br><span class="line">        Long ceil=set.ceiling((<span class="keyword">long</span>)nums[i]-(<span class="keyword">long</span>)t);</span><br><span class="line">        <span class="keyword">if</span>(ceil!=<span class="keyword">null</span> &amp;&amp; ceil&lt;=(<span class="keyword">long</span>)nums[i]+(<span class="keyword">long</span>)t) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        set.add((<span class="keyword">long</span>)nums[i]);</span><br><span class="line">        <span class="keyword">if</span> (set.size()&gt;k) &#123;</span><br><span class="line">            set.remove((<span class="keyword">long</span>)nums[i-k]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>43ms，56%左右，依然要注意溢出的问题</p>
<h2 id="1282-用户分组"><a href="#1282-用户分组" class="headerlink" title="1282. 用户分组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to/" >1282. 用户分组<i class="fas fa-external-link-alt"></i></a></h2><p>有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。</p>
<p>你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：groupSizes = [<span class="number">3</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">1</span>,<span class="number">3</span>]</span><br><span class="line">输出：[[<span class="number">5</span>],[<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>],[<span class="number">3</span>,<span class="number">4</span>,<span class="number">6</span>]]</span><br><span class="line">解释： </span><br><span class="line">其他可能的解决方案有 [[<span class="number">2</span>,<span class="number">1</span>,<span class="number">6</span>],[<span class="number">5</span>],[<span class="number">0</span>,<span class="number">4</span>,<span class="number">3</span>]] 和 [[<span class="number">5</span>],[<span class="number">0</span>,<span class="number">6</span>,<span class="number">2</span>],[<span class="number">4</span>,<span class="number">3</span>,<span class="number">1</span>]]。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：groupSizes = [<span class="number">2</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">2</span>]</span><br><span class="line">输出：[[<span class="number">1</span>],[<span class="number">0</span>,<span class="number">5</span>],[<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>]]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>groupSizes.length == n</code></li>
<li><code>1 &lt;= n &lt;= 500</code></li>
<li><code>1 &lt;= groupSizes[i] &lt;= n</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>12.8周赛的题，我是模拟做的，看了别人的做法还是感觉这种比较优雅</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; groupThePeople(<span class="keyword">int</span>[] groupSizes) &#123;</span><br><span class="line">    HashMap&lt;Integer,List&lt;Integer&gt;&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;groupSizes.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!map.containsKey(groupSizes[i])) &#123;</span><br><span class="line">            List&lt;Integer&gt; list=<span class="keyword">new</span> LinkedList();</span><br><span class="line">            map.put(groupSizes[i],list);</span><br><span class="line">        &#125;</span><br><span class="line">        List&lt;Integer&gt; gl=map.get(groupSizes[i]);</span><br><span class="line">        gl.add(i);</span><br><span class="line">        <span class="keyword">if</span> (gl.size()==groupSizes[i]) &#123;</span><br><span class="line">            res.add(gl);</span><br><span class="line">            map.remove(groupSizes[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>时间复杂度<code>O(N)</code></p>
<p><strong>解法二</strong></p>
<p>模拟的解法，时间复杂度<code>O(N^2)</code></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; groupThePeople(<span class="keyword">int</span>[] groupSizes) &#123;</span><br><span class="line">    <span class="keyword">boolean</span>[] visit=<span class="keyword">new</span> <span class="keyword">boolean</span>[groupSizes.length];</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;groupSizes.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (visit[i]) &#123;</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        List&lt;Integer&gt; list= <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        list.add(i);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;groupSizes.length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (visit[j]) &#123;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (list.size()==groupSizes[i]) &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (groupSizes[j]==groupSizes[i]) &#123;</span><br><span class="line">                list.add(j);</span><br><span class="line">                visit[j]=<span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        res.add(list);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="128-最长连续序列"><a href="#128-最长连续序列" class="headerlink" title="128. 最长连续序列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-consecutive-sequence/" >128. 最长连续序列<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个未排序的整数数组，找出最长连续序列的长度。</p>
<p>要求算法的时间复杂度为 <code>O(n)</code>。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">100</span>, <span class="number">4</span>, <span class="number">200</span>, <span class="number">1</span>, <span class="number">3</span>, <span class="number">2</span>]</span><br><span class="line">输出: <span class="number">4</span></span><br><span class="line">解释: 最长连续序列是 [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>]。它的长度为 <span class="number">4</span>。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>借助Hash表的暴力解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestConsecutive</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums ==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> n:nums) &#123;</span><br><span class="line">        set.add(n);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> num=nums[i];</span><br><span class="line">        <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(set.contains(num+<span class="number">1</span>))&#123;</span><br><span class="line">            res++;</span><br><span class="line">            num++;</span><br><span class="line">        &#125;</span><br><span class="line">        max=Math.max(max,res);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>对于每个元素在Hash表中查找它的下一个连续的元素<code>num+1</code> 有没有，有的话就继续往下找，最后求的以每个元素开头的最长子序列长度，时间复杂度<code>O(N^2)</code>不符合题目的要求</p>
<p>所以我们需要优化我们的算法，其实上面的过程我们很容易就看出啦里面会有重复的计算</p>
<p><code>eg. 5，4，6，7，8</code>  我们在第一个5的时候计算了以5开头的 5，6，7，8这条路径，然后转而计算第二个4，计算了以4开头的4，5，6，7，8这里其实就发生了重复的计算，那么我们这里求的是最长的序列，所以我们需要舍弃第一个，也就是说我们遍历第一个5的时候直接跳过，跳过的依据就是判断 5-1 在不在集合中，如果在那么以它开头的序列一定不是不会是最长的，反之则有可能是最长的，我们统计所有这样的序列长度，最后求一个最大值就可以了</p>
<p><strong>解法二</strong></p>
<p>每个元素最多遍历2次，所以时间复杂度为O(N)符合要求</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestConsecutive</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums ==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> n:nums) &#123;</span><br><span class="line">        set.add(n);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> num=nums[i];</span><br><span class="line">        <span class="keyword">if</span> (!set.contains(num-<span class="number">1</span>)) &#123;</span><br><span class="line">            <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">while</span>(set.contains(num+<span class="number">1</span>))&#123;</span><br><span class="line">                res++;</span><br><span class="line">                num++;</span><br><span class="line">            &#125;</span><br><span class="line">            max=Math.max(max,res);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法三</strong></p>
<p>并查集的解法，略微麻烦点，但是毕竟这题的tag就是并查集，还是实现一下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//并查集</span></span><br><span class="line">HashMap&lt;Integer,Integer&gt; parent;</span><br><span class="line"></span><br><span class="line">HashMap&lt;Integer,Integer&gt; size;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> max=<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(parent.get(index)!=index)&#123;</span><br><span class="line">        <span class="comment">//parent[index]=parent[parent[index]];</span></span><br><span class="line">        parent.put(index,parent.get(index));</span><br><span class="line">        index=parent.get(index);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pID=find(p);</span><br><span class="line">    <span class="keyword">int</span> qID=find(q);</span><br><span class="line">    <span class="keyword">if</span> (pID==qID) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> pSize=size.get(pID);</span><br><span class="line">    <span class="keyword">int</span> qSize=size.get(qID);</span><br><span class="line">    <span class="keyword">if</span> (pSize &gt; qSize) &#123;</span><br><span class="line">        <span class="comment">//parent[qID]=pID;</span></span><br><span class="line">        parent.put(qID,pID);</span><br><span class="line">        <span class="comment">//size[pID]+=size[qID];</span></span><br><span class="line">        size.put(pID,pSize+qSize);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="comment">//parent[pID]=qID;</span></span><br><span class="line">        parent.put(pID,qID);</span><br><span class="line">        <span class="comment">//size[qID]+=size[pID];</span></span><br><span class="line">        size.put(qID,pSize+qSize);</span><br><span class="line">    &#125;</span><br><span class="line">    max=Math.max(max,pSize+qSize); <span class="comment">//统计最大值</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">initUnionFind</span><span class="params">(<span class="keyword">int</span>[]nums)</span></span>&#123;</span><br><span class="line">    parent=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    size=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        parent.put(nums[i],nums[i]);</span><br><span class="line">        size.put(nums[i],<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestConsecutive</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums ==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        set.add(nums[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    initUnionFind(nums);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (set.contains(nums[i]-<span class="number">1</span>)) &#123; <span class="comment">//判断-1或者+1都可以</span></span><br><span class="line">            union(nums[i],nums[i]-<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1002-查找常用字符"><a href="#1002-查找常用字符" class="headerlink" title="1002. 查找常用字符"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-common-characters/" >1002. 查找常用字符<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>简单</strong></p>
<p>给定仅有小写字母组成的字符串数组 <code>A</code>，返回列表中的每个字符串中都显示的全部字符（<strong>包括重复字符</strong>）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。</p>
<p>你可以按任意顺序返回答案。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：[&quot;bella&quot;,&quot;label&quot;,&quot;roller&quot;]</span><br><span class="line">输出：[&quot;e&quot;,&quot;l&quot;,&quot;l&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：[&quot;cool&quot;,&quot;lock&quot;,&quot;cook&quot;]</span><br><span class="line">输出：[&quot;c&quot;,&quot;o&quot;]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li> <code>1 &lt;= A.length &lt;= 100</code></li>
<li> <code>1 &lt;= A[i].length &lt;= 100</code></li>
<li> <code>A[i][j]</code> 是小写字母</li>
</ol>
<p><strong>解法一</strong></p>
<p>范围小，随便搞</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">commonChars</span><span class="params">(A []<span class="keyword">string</span>)</span> []<span class="title">string</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> m = <span class="built_in">make</span>(<span class="keyword">map</span>[<span class="keyword">int</span>]<span class="keyword">map</span>[<span class="keyword">byte</span>]<span class="keyword">int</span>)</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">var</span> max = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(A); i++ &#123;</span><br><span class="line">        m[i] = <span class="built_in">make</span>(<span class="keyword">map</span>[<span class="keyword">byte</span>]<span class="keyword">int</span>)</span><br><span class="line">        <span class="keyword">for</span> j := <span class="number">0</span>; j &lt; <span class="built_in">len</span>(A[i]); j++ &#123;</span><br><span class="line">            m[i][A[i][j]]++</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> <span class="built_in">len</span>(A[i]) &gt; <span class="built_in">len</span>(A[max]) &#123;</span><br><span class="line">            max = i</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">var</span> res []<span class="keyword">string</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(A[max]); i++ &#123;</span><br><span class="line">        <span class="keyword">var</span> flag = <span class="literal">true</span></span><br><span class="line">        <span class="keyword">for</span> j := <span class="number">0</span>; j &lt; <span class="built_in">len</span>(A); j++ &#123;</span><br><span class="line">            <span class="keyword">if</span> j == max &#123;</span><br><span class="line">                <span class="keyword">continue</span></span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> m[j][A[max][i]] == <span class="number">0</span> &#123;</span><br><span class="line">                flag = <span class="literal">false</span></span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line">            &#125;</span><br><span class="line">            m[j][A[max][i]]--</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> flag &#123;</span><br><span class="line">            res = <span class="built_in">append</span>(res, <span class="keyword">string</span>(A[max][i]))</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="前缀和相关"><a href="#前缀和相关" class="headerlink" title="前缀和相关"></a><em>前缀和相关</em></h2><h2 id="560-和为K的子数组"><a href="#560-和为K的子数组" class="headerlink" title="560. 和为K的子数组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/subarray-sum-equals-k/" >560. 和为K的子数组<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。</p>
<p><strong>示例 1 :</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:nums = [<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>], k = <span class="number">2</span></span><br><span class="line">输出: <span class="number">2</span> , [<span class="number">1</span>,<span class="number">1</span>] 与 [<span class="number">1</span>,<span class="number">1</span>] 为两种不同的情况。</span><br></pre></td></tr></table></figure>


<p><strong>说明 :</strong></p>
<ul>
<li>数组的长度为 [1, 20,000]。</li>
<li>数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。</li>
</ul>
<p><strong>解法一</strong></p>
<p>前缀和 + hash表</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">subarraySum</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    map.put(<span class="number">0</span>,<span class="number">1</span>);<span class="comment">//初始化头哨兵,避免下标转换</span></span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>,res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        sum+=nums[i];</span><br><span class="line">        <span class="comment">//-1 -1 1 | 0</span></span><br><span class="line">        <span class="keyword">if</span> (<span class="comment">/*sum&gt;=k &amp;&amp; */</span>map.containsKey(sum-k)) &#123;</span><br><span class="line">            res+=map.get(sum-k);</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(sum,map.getOrDefault(sum,<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>我们将各个位置的前缀和作为键，这个前缀和在<strong>当前位置之前出现的次数作为键</strong> (这一点保证了连续，不会找到后面去)</p>
<p>然后我们的目标就是找到和为k区间有多少个，区间和利用前缀和可以直接算出，也就是 </p>
<p><code>sum[i~j] = sum[j] -sum[i]= k</code> 然后这个问题就可以转换为，当我们遍历到某个元素的时候，我们在map中查找前缀和为<code>sum[j] - k</code>的元素有几个，这样就可以得到区间和为k的区间有多少个！</p>
<p>值得注意的地方就是，需要添加一个初始的<code>sum=0</code>的值，避免下标的转换</p>
<p>画个图就像下面这样：</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20191104/ECiyYqso8i2K.png?imageslim"
                      alt="img"
                ></p>
<h2 id="1248-统计「优美子数组」"><a href="#1248-统计「优美子数组」" class="headerlink" title="1248. 统计「优美子数组」"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/count-number-of-nice-subarrays/" >1248. 统计「优美子数组」<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个整数数组 nums 和一个整数 k。</p>
<p>如果某个子数组中恰好有 k 个奇数数字，我们就认为这个子数组是<strong>「优美子数组」</strong>。</p>
<p>请返回这个数组中「优美子数组」的数目。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">1</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>], k = <span class="number">3</span></span><br><span class="line">输出：<span class="number">2</span></span><br><span class="line">解释：包含 <span class="number">3</span> 个奇数的子数组是 [<span class="number">1</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>] 和 [<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>] 。</span><br></pre></td></tr></table></figure>


<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">2</span>,<span class="number">4</span>,<span class="number">6</span>], k = <span class="number">1</span></span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：数列中不包含任何奇数，所以不存在优美子数组。</span><br></pre></td></tr></table></figure>


<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">2</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">2</span>], k = <span class="number">2</span></span><br><span class="line">输出：<span class="number">16</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 50000</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10^5</code></li>
<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>11.3 周赛第二题，没做出来，以为是滑动窗口，滑了半天没滑出来，后来看了解答知道了是利用前缀和 + Hash，其实和上面一题是类似的，相当于上一题的进阶</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numberOfSubarrays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>,res=<span class="number">0</span>;</span><br><span class="line">    map.put(<span class="number">0</span>,<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[i]%<span class="number">2</span>==<span class="number">1</span>) &#123;</span><br><span class="line">            sum++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//题目说了都是正数，所以可以优化下</span></span><br><span class="line">        <span class="keyword">if</span> (sum&gt;=k &amp;&amp; map.containsKey(sum-k)) &#123;</span><br><span class="line">            res+=map.get(sum-k);</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(sum,map.getOrDefault(sum,<span class="number">0</span>)+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实这里就是把奇数都看作 1，偶数都看作0，这样问题就变成了求和为k的区间个数有多少个，然后在根据上面的前缀和+Hash表，就可以很容易的得到答案，还有一点就是题目说了数据都是正数，所以在判断的时候可以加一个<code>sum&gt;=k</code> 来减少一点判断，当然这题题目指定了数据的范围，所以还可以直接用数组做map映射</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//update: 2020.4.21 之前的数组开大了，开了10w。。。</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numberOfSubarrays</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] map=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">50001</span>];  </span><br><span class="line">    map[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++)&#123;</span><br><span class="line">        sum+=nums[i]&amp;<span class="number">1</span>;</span><br><span class="line">        map[sum]++;</span><br><span class="line">        <span class="comment">//sum-x=k</span></span><br><span class="line">        <span class="keyword">if</span>(sum-k &gt;=<span class="number">0</span> &amp;&amp; map[sum-k]!=<span class="number">0</span>)&#123;</span><br><span class="line">            res+=map[sum-k];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>这题还有其他的数学解法，暂时不太想写，后面有时间再写吧，大致思路就是</p>
<p>[2，2，1，1，2，2，2] res=3*4=12</p>
</blockquote>
<h2 id="1371-每个元音包含偶数次的最长子字符串"><a href="#1371-每个元音包含偶数次的最长子字符串" class="headerlink" title="1371. 每个元音包含偶数次的最长子字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/" >1371. 每个元音包含偶数次的最长子字符串<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个字符串 <code>s</code> ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;eleetminicoworoep&quot;</span></span><br><span class="line">输出：<span class="number">13</span></span><br><span class="line">解释：最长子字符串是 <span class="string">&quot;leetminicowor&quot;</span> ，它包含 e，i，o 各 <span class="number">2</span> 个，以及 <span class="number">0</span> 个 a，u 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;leetcodeisgreat&quot;</span></span><br><span class="line">输出：<span class="number">5</span></span><br><span class="line">解释：最长子字符串是 <span class="string">&quot;leetc&quot;</span> ，其中包含 <span class="number">2</span> 个 e 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;bcbcbc&quot;</span></span><br><span class="line">输出：<span class="number">6</span></span><br><span class="line">解释：这个示例中，字符串 <span class="string">&quot;bcbcbc&quot;</span> 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 <span class="number">0</span> 次。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 5 x 10^5</code></li>
<li><code>s</code> 只包含小写英文字母。</li>
</ul>
<p><strong>解法一</strong></p>
<p>这题挺好的，反正我是想不出来这样的解法，一开始以为是滑动窗口，写了几行代码发现行不通，数据范围这么大，感觉不是很简单，然后就直接看答案了，涉及到<strong>前缀和</strong>以及<strong>状态压缩</strong>，前缀和维护元音字符出现的奇偶性，并压缩成一个整数，核心思想就是<code>奇数-奇数=偶数</code>，<code>偶数-偶数=偶数</code>，所以如果两个不同位置的状态相同，那么中间的部分出现次数一定是偶数，具体的不想多解释了看看 <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/mei-ge-yuan-yin-bao-han-ou-shu-ci-de-zui-chang-z-2/" >官方题解<i class="fas fa-external-link-alt"></i></a> 就行了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findTheLongestSubstring</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//a e i o u</span></span><br><span class="line">    <span class="comment">//32种状态</span></span><br><span class="line">    <span class="keyword">int</span>[] pre=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">1</span>&lt;&lt;<span class="number">5</span>];</span><br><span class="line">    Arrays.fill(pre,-<span class="number">1</span>);</span><br><span class="line">    pre[<span class="number">0</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> state=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;s.length();i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;a&#x27;</span>) state^=<span class="number">16</span>;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;e&#x27;</span>) state^=<span class="number">8</span>;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;i&#x27;</span>) state^=<span class="number">4</span>;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;o&#x27;</span>) state^=<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==<span class="string">&#x27;u&#x27;</span>) state^=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span>(pre[state]!=-<span class="number">1</span>)&#123;</span><br><span class="line">            res=Math.max(res,i+<span class="number">1</span>-pre[state]);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            pre[state]=i+<span class="number">1</span>; <span class="comment">//前i个字符的状态</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="974-和可被-K-整除的子数组"><a href="#974-和可被-K-整除的子数组" class="headerlink" title="974. 和可被 K 整除的子数组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/" >974. 和可被 K 整除的子数组<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组 <code>A</code>，返回其中元素之和可被 <code>K</code> 整除的（连续、非空）子数组的数目。</p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：A = [<span class="number">4</span>,<span class="number">5</span>,<span class="number">0</span>,-<span class="number">2</span>,-<span class="number">3</span>,<span class="number">1</span>], K = <span class="number">5</span></span><br><span class="line">输出：<span class="number">7</span></span><br><span class="line">解释：</span><br><span class="line">有 <span class="number">7</span> 个子数组满足其元素之和可被 K = <span class="number">5</span> 整除：</span><br><span class="line">[<span class="number">4</span>, <span class="number">5</span>, <span class="number">0</span>, -<span class="number">2</span>, -<span class="number">3</span>, <span class="number">1</span>], [<span class="number">5</span>], [<span class="number">5</span>, <span class="number">0</span>], [<span class="number">5</span>, <span class="number">0</span>, -<span class="number">2</span>, -<span class="number">3</span>], [<span class="number">0</span>], [<span class="number">0</span>, -<span class="number">2</span>, -<span class="number">3</span>], [-<span class="number">2</span>, -<span class="number">3</span>]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= A.length &lt;= 30000</code></li>
<li><code>-10000 &lt;= A[i] &lt;= 10000</code></li>
<li><code>2 &lt;= K &lt;= 10000</code></li>
</ol>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//同余定义 (b-a)%k=0 =&gt; b%k==a%k</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">subarraysDivByK</span><span class="params">(<span class="keyword">int</span>[] A, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] pre=<span class="keyword">new</span> <span class="keyword">int</span>[K];</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    pre[sum]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> a:A)&#123;</span><br><span class="line">        sum=(sum+a)%K;</span><br><span class="line">        <span class="comment">//Java被除数为负数的时候取模也是负数</span></span><br><span class="line">        <span class="comment">//这里应该纠正，避免负数的模</span></span><br><span class="line">        <span class="keyword">if</span>(sum&lt;<span class="number">0</span>) sum+=K;</span><br><span class="line">        res+=pre[sum];</span><br><span class="line">        pre[sum]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode查找</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-09-15 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/09/15/ae50c318/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/09/24/c279d77a/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">AQS源码解析（上）</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2019/09/05/18643927/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">深入理解Java虚拟机(三)</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/09/15/ae50c318/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="nav-number">1.</span> <span class="nav-text">1. 两数之和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#349-%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86"><span class="nav-number">2.</span> <span class="nav-text">349. 两个数组的交集</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#350-%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86-II"><span class="nav-number">3.</span> <span class="nav-text">350. 两个数组的交集 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#242-%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D"><span class="nav-number">4.</span> <span class="nav-text">242. 有效的字母异位词</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1160-%E6%8B%BC%E5%86%99%E5%8D%95%E8%AF%8D"><span class="nav-number">5.</span> <span class="nav-text">1160. 拼写单词</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#202-%E5%BF%AB%E4%B9%90%E6%95%B0"><span class="nav-number">6.</span> <span class="nav-text">202. 快乐数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#290-%E5%8D%95%E8%AF%8D%E8%A7%84%E5%BE%8B"><span class="nav-number">7.</span> <span class="nav-text">290. 单词规律</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#205-%E5%90%8C%E6%9E%84%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">8.</span> <span class="nav-text">205. 同构字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#454-%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0-II"><span class="nav-number">9.</span> <span class="nav-text">454. 四数相加 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#451-%E6%A0%B9%E6%8D%AE%E5%AD%97%E7%AC%A6%E5%87%BA%E7%8E%B0%E9%A2%91%E7%8E%87%E6%8E%92%E5%BA%8F"><span class="nav-number">10.</span> <span class="nav-text">451. 根据字符出现频率排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#49-%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D%E5%88%86%E7%BB%84"><span class="nav-number">11.</span> <span class="nav-text">49. 字母异位词分组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#447-%E5%9B%9E%E6%97%8B%E9%95%96%E7%9A%84%E6%95%B0%E9%87%8F"><span class="nav-number">12.</span> <span class="nav-text">447. 回旋镖的数量</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#217-%E5%AD%98%E5%9C%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0"><span class="nav-number">13.</span> <span class="nav-text">217. 存在重复元素</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#220-%E5%AD%98%E5%9C%A8%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0-III"><span class="nav-number">14.</span> <span class="nav-text">220. 存在重复元素 III</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1282-%E7%94%A8%E6%88%B7%E5%88%86%E7%BB%84"><span class="nav-number">15.</span> <span class="nav-text">1282. 用户分组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#128-%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E5%BA%8F%E5%88%97"><span class="nav-number">16.</span> <span class="nav-text">128. 最长连续序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1002-%E6%9F%A5%E6%89%BE%E5%B8%B8%E7%94%A8%E5%AD%97%E7%AC%A6"><span class="nav-number">17.</span> <span class="nav-text">1002. 查找常用字符</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%89%8D%E7%BC%80%E5%92%8C%E7%9B%B8%E5%85%B3"><span class="nav-number">18.</span> <span class="nav-text">前缀和相关</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#560-%E5%92%8C%E4%B8%BAK%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84"><span class="nav-number">19.</span> <span class="nav-text">560. 和为K的子数组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1248-%E7%BB%9F%E8%AE%A1%E3%80%8C%E4%BC%98%E7%BE%8E%E5%AD%90%E6%95%B0%E7%BB%84%E3%80%8D"><span class="nav-number">20.</span> <span class="nav-text">1248. 统计「优美子数组」</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1371-%E6%AF%8F%E4%B8%AA%E5%85%83%E9%9F%B3%E5%8C%85%E5%90%AB%E5%81%B6%E6%95%B0%E6%AC%A1%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">21.</span> <span class="nav-text">1371. 每个元音包含偶数次的最长子字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#974-%E5%92%8C%E5%8F%AF%E8%A2%AB-K-%E6%95%B4%E9%99%A4%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84"><span class="nav-number">22.</span> <span class="nav-text">974. 和可被 K 整除的子数组</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
